1. Two Sum

题目描述

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

示例:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解答

这道题的暴力解法是用双重循环，遍历数组找到和为target的两个数的下标，这样的复杂度为O($n^2$)。

我们还可以先把数组排序一遍，然后用两个指针（two pointer）的方法来做，这个的时间复杂度为O($nlogn$)。

最快的一种算法是，先建立一个map，然后遍历数组，对于遇见的每一个数num，判断target - num 是否在这个map里面，则输出这两个数的下标，时间复杂度为O($n$)。

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    	unordered_map <int, int> umap;
    	for (int i = 0; i < nums.size(); i ++) {
    		if (umap.find(target - nums[i]) == umap.end())
    			umap[nums[i]] = i;
    		else
    			return vector<int>{umap[target - nums[i]], i};
    	}
    return -1;
    }
};